class Solution(object):
    def placeWordInCrossword(self, board, word):
        m = len(board)
        n = len(board[0])
        q = len(word)
        for i in range(m):
            left = 0
            right = 0
            l_list = []
            while right < n:
                if board[i][right] == '#':
                    if right - left == len(word):
                        if not l_list:
                            return True
                        else:
                            flag = True
                            for id in l_list:
                                if board[i][id] != word[id - left]:
                                    flag = False
                                    break
                            if flag:
                                return True
                            flag = True
                            for id in l_list:
                                if board[i][id] != word[q - 1 - (id - left)]:
                                    flag = False
                                    break
                            if flag:
                                return True
                    l_list = []
                    right += 1
                    left = right
                else:
                    if board[i][right] != ' ':
                        l_list.append(right)
                    right += 1
            if right - left == len(word):
                if not l_list:
                    return True
                else:
                    flag = True
                    for id in l_list:
                        if board[i][id] != word[id - left]:
                            flag = False
                            break
                    if flag:
                        return True
                    flag = True
                    for id in l_list:
                        if board[i][id] != word[q - 1 - (id - left)]:
                            flag = False
                            break
                    if flag:
                        return True
        for j in range(n):
            left = 0
            right = 0
            l_list = []
            while right < m:
                if board[right][j] == '#':
                    if right - left == len(word):
                        if not l_list:
                            return True
                        else:
                            flag = True
                            for id in l_list:
                                if board[id][j] != word[id - left]:
                                    flag = False
                                    break
                            if flag:
                                return True
                            flag = True
                            for id in l_list:
                                if board[id][j] != word[q - 1 - (id - left)]:
                                    flag = False
                                    break
                            if flag:
                                return True
                    l_list = []
                    right += 1
                    left = right
                else:
                    if board[right][j] != ' ':
                        l_list.append(right)
                    right += 1
            if right - left == len(word):
                if not l_list:
                    return True
                else:
                    flag = True
                    for id in l_list:
                        if board[id][j] != word[id - left]:
                            flag = False
                            break
                    if flag:
                        return True
                    flag = True
                    for id in l_list:
                        if board[id][j] != word[q - 1 - (id - left)]:
                            flag = False
                            break
                    if flag:
                        return True
        return False


data = Solution()
board = [["#"," ","#"],["#"," ","#"],["#"," ","c"]]
word = 'ca'
print(data.placeWordInCrossword(board, word))
